package leetcode;

import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //因为arr2是不重复的元素，所以用集合接收一下arr2
        Set<Integer> set = new HashSet<>();
        for (int val : arr2) {
            set.add(val);
        }
        //用快速排序给arr1升序排序
        Arrays.sort(arr1);
        //queue用来接收arr2中存在的数据，queue1用来接收arr2中不存在的数据
        Queue<Integer> queue = new ArrayDeque<>();
        Queue<Integer> queue1 = new ArrayDeque<>();
        for (int i = 0; i < arr1.length; i++) {
            if (set.contains(arr1[i])) {
                queue.add(arr1[i]);
            } else {
                queue1.add(arr1[i]);
            }
        }
        //arr用作返回数组，arr3用来放放置queue中的数据，arr4用来放置queue1中的数据
        int[] arr = new int[arr1.length];
        int[] arr3 = new int[queue.size()];
        int[] arr4 = new int[queue1.size()];
        for (int i = 0; i < arr3.length; i++) {
            arr3[i] = queue.poll();
        }
        for (int i = 0; i < arr4.length; i++) {
            arr4[i] = queue1.poll();
        }
        Queue<Integer> queue2 = new ArrayDeque<>();
        Queue<Integer> queue3 = new ArrayDeque<>();
        for (int val : arr2) {
            queue2.add(val);
        }

        while (queue2 != null) {
            if (queue2.size() == 0){
                break;
            }
            for (int i = 0; i < arr3.length; i++) {
                if (queue2.peek() == arr3[i]) {
                    queue3.add(arr3[i]);
                }
            }
            queue2.poll();
        }

        for (int i = 0; i < arr4.length; i++) {
            queue3.add(arr4[i]);
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = queue3.poll();
        }

        return arr;
    }
}

public class Test1 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr1 = new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
        int[] arr2 = new int[]{2, 1, 4, 3, 9, 6};
        int[] arr = new int[arr1.length];
        arr = solution.relativeSortArray(arr1, arr2);
        for (int val : arr) {
            System.out.print(val + " ");
        }
    }
}
